package pri.hillchen.algorithm.array;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode #330	Patching Array  :
 * 解题思路：假设在添加元素前数组中元素可以表达最大的连续区域值为currentRange,则当添加任意一个在[1,currentRange+1]
 * 范围内的元素patch后的数组，可以表达的最大连续区域值为(currentRange+crrPatch),假设maxPatch=currentRange+1,
 * 所以当添加假设maxPatch可获取的连续区域最大，而当添加原数组中的元素就计算在补丁数组之内。
 * 所以添加补丁的原则是：当原数组中存在没有使用过的元素 element 小于等于maxPatch，在添加原数组元素，如果不存在则添加maxPatch
 * Created by hillchen on 2017/9/27 0027.
 */
public class PatchingArray {
    public List<Integer> patchingArray(int[] arrays, int target){
        List<Integer> ret = new ArrayList<Integer>();
        int currRange = 0;
        int lastRange = -1;
        int currArrayIndex = 0;
        int maxPatch = 1;
        while(currRange > lastRange  && currRange < target) { //注意原数组下标越界和currRange溢出
            lastRange = currRange;
            if(currArrayIndex < arrays.length && arrays[currArrayIndex] <= maxPatch){
                currRange += arrays[currArrayIndex];
                currArrayIndex ++;
            }else{
                currRange += maxPatch;
                ret.add(maxPatch);
            }
            maxPatch = currRange + 1;
        }
        return ret;
    }

    public static void main(String[] args){
        PatchingArray patchingArray = new PatchingArray();
        int[] arrays4 = {1,2,31,33};
        List<Integer> patch4 =  patchingArray.patchingArray(arrays4,2147483647);
        patchingArray.printList(patch4);

    }

    public void printList(List<Integer> list){
        StringBuilder sb = new StringBuilder();
        boolean needSplit = false;
        for(Integer element : list){
            if(needSplit){
                sb.append(",");
            }else{
                needSplit = true;
            }
            sb.append(element);
        }
        System.out.println(sb.toString());
    }
}
